// https://leetcode.cn/problems/snakes-and-ladders/description/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用广度优先搜索模拟棋盘游戏过程
// 2. 按层遍历，每层代表一次骰子投掷
// 3. 处理蛇和梯子的跳跃逻辑，更新目标位置
// 4. 计算棋盘坐标时考虑之字形排列规则
// 5. 时间复杂度：O(N²)，空间复杂度：O(N²)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <queue>

class Solution 
{
public:
    int snakesAndLadders(vector<vector<int>>& board) 
    {
        int n = board.size();
        int totalSize = n * n;

        vector<bool> visited(totalSize + 1, false);
        visited[1] = true;

        queue<int> q;
        q.push(1);

        int steps = 0;
        while (!q.empty())
        {
            int levelSize = q.size();
            for (int i = 0 ; i < levelSize ; i++)
            {
                int cur = q.front();
                q.pop();

                if (cur == totalSize)
                {
                    return steps;
                }

                for (int dis = 1; dis <= 6 ; dis++)
                {
                    int next = cur + dis;
                    
                    if (next > totalSize)
                    {
                        break;
                    }

                    int row = n - 1 - (next - 1) / n;
                    int col = (next - 1) % n;
                    if ((n - row - 1) % 2 == 1)
                    {
                        col = n - 1 - col;
                    }

                    if (board[row][col] != -1)
                    {
                        next = board[row][col];
                    }

                    if (!visited[next])
                    {
                        visited[next] = true;
                        q.push(next);
                    }
                }
            }
            steps++;
        }

        return -1;
    }
};

int main()
{
    // 4
    vector<vector<int>> board1 = {
        {-1,-1,-1,-1,-1,-1},
        {-1,-1,-1,-1,-1,-1},
        {-1,-1,-1,-1,-1,-1},
        {-1,35,-1,-1,13,-1},
        {-1,-1,-1,-1,-1,-1},
        {-1,15,-1,-1,-1,-1}
    };

    // 2
    vector<vector<int>> board2 = {
        {-1,-1,-1},
        {-1,-1,-1},
        {-1,-1,-1}
    };

    Solution sol;

    cout << sol.snakesAndLadders(board1) << endl;
    cout << sol.snakesAndLadders(board2) << endl;

    return 0;
}